The general flow of a logic synthesizing process is illustrated in FIG. 1. The inputs may be applied in the form of a truth table representing a logical function of an object circuit, a logical expression in a two-stage sum-of-products form or a logical expression in a multistage network form (as shown in FIG. 2, each portion in the network that corresponds to one logical expression is called a node) in which truth tables or logical expressions for respective stages are combined. The final output is provided in the form of a net list of gate cells depending on a gate-array or standard-cell technology.
FIG. 2 illustrates an example of the multistage network of logical expressions in FIG. 1. More specifically, FIG. 2 illustrates a multistage logic circuit with inputs x.sub.1, x.sub.2 and outputs y.sub.1, y.sub.2. Each of three nodes 1, 2 and 3 corresponds to one logical expression.
Various internal processing systems have been proposed for a logic Synthesizing process such as that shown in FIG. 1. In general, the system is divided into a portion, such as that shown in FIG. 2, adapted to create a multistage network of technology-independent logical expressions and a portion adapted to convert the network to actual circuits. Hereinafter, the technology-independent process will be mainly described.
In the technology-independent process, a given logical expression is converted to a simpler logical expression (the term "simple" means that the number of factors used in a logical expression is small.). A common part is factored out from the logical expression, thereby creating a desired multistage logic network (which is called a logic synthesis or a logic optimizing process).
FIGS. 3(a) and 3(b) illustrate examples of the logic optimizing process. More specifically, FIG. 3(a) illustrates an example of a simplification in which f=ab+bc+ac is simplified such that ##EQU1## In the case of FIG. 3(b), ab and c+d, which appear repeatedly, are replaced with new variables x and y, respectively, and common parts are factored out.
Such processes are all performed by changing the expressions on a symbolic manipulation basis. Since those expressions are Boolean algebraic expressions, the simplification and factoring should be defined in accordance with Boolean algebra. However, changing expressions based on Boolean algebra is very costly (with respect to calculation time and memories used), and the processes as shown in FIG. 3 also cause a lot of trouble in calculation in proportion to the exponents of the input variables in the worst case. For high-speed processes, therefore, these expressions may be regarded as normal algebraic expressions. 0f course, normal algebraic expressions and Boolean algebraic expressions have no identical property. For instance, a+a=a and aa=a in Boolean algebra, while, according to normal algebraic expressions, a+a=2a a.sup.2. Thus, when f=ad+bcd+e and g =a+b, f can be expressed as f=gd(a+c)+e in the Boolean algebra. But, f cannot be expressed by use of g in normal algebra. Also, since a certain variable and its negation cannot be recognized, conversion utilizing the theorem of a+a=1 cannot be performed. Having such drawbacks, a circuit automatically synthesized by use of only processes based on normal algebra is inferior, in circuit scale, to a circuit resulting from automatic synthesis using the rules of Boolean algebra.
Several methods of performing Boolean algebraic processes have been proposed in order to create high-quality circuits. One of them is a method based on simplification of a two-stage sum-of-products logical expression (hereinafter referred to as method A), according to which the "don't care condition" for each node in a network is utilized for simplification of the node and factoring. There is a case in which a particular combination of node values never occurs in a multistage network and a case where output node values do not affect values at the external output terminal. Thus, the "don't care conditions" for each node are expressed in the form of a sum-of-products logical expression using external inputs and intermediate nodes. Even if the logic function of the node is changed due to some transformation of the expression, when the "don't care conditions" involve the case in which a change occurs, the transformation will not alter the logic function of the entire circuit (a combination of such values cannot occur or the effect of such change does not arrive at the output). Thus, the use of the "don't care conditions" will permit more powerful simplification and factoring.
FIG. 4 illustrates an example of the "don't care conditions" of the method A. In the Figure, since, for example, at node 4, its output j is the inverse signal of an input g, combinations of j=0, g =0; and j=1, g=0 cannot occur. Thus, D=g.multidot.j+g.multidot.j becomes effective as the don't-care condition for all the nodes.
The time required for calculation in the method is proportional to the square of the number of product terms (in the case of a+bc, a and bc are product terms) in a logical expression involving a don't-care condition. Thus, high-speed processing will be made possible if a compact expression using a sum-of-products logical expression is allowed. Since the number of product terms in a sum-of-products logical expression representing don't-care conditions in a normal multistage logic network is very large, a device for reducing the number of product terms representing don't care has been proposed in order to perform a process within a practical period (of course, the capability decreases as compared with the case where a complete don't-care conditions is used).
According to another method, an actual logic function and a don't-care condition of a node are defined as a vector (the so-called a truth table) for a set of values of external inputs (hereinafter referred to as method B).
FIG. 5 illustrates an example of don't-care conditions in method B. In this example, a V.sub.1 and V.sub.2 are input and V.sub.5 is output. For example, EQU f.sub.5 =[0,0,1,1]
represents that the output V.sub.5 changes in the order of 0, 0, 1, 1 when the input V.sub.1 changes in the order of 0, 0, 1, 1, while the input V.sub.2 changes in the order of 0, 1, 0, 1.
In FIG. 5, the logic of the output V.sub.5 (which is herein the same as that of V.sub.4) is needed for the logic of the inputs V.sub.1 and V.sub.2. There is no need for the logic of the node 8. Thus, any logic that gates of the inside of the circuit (the node 8 in this case) can take can be obtained within the range in which the logic of the output V.sub.5 remains unchanged. Such logic is called a permissible function. That is, for the node 9, since V.sub.3 =1 is possible when V.sub.1 =1 and V.sub.2 =0, and V.sub.3 =0 is also possible when V.sub.1 =V.sub.2 =1, EQU f.sub.3 =[0, 0, 1, 0 ]
can be written. Thus, the permissible function for the logic of the output V.sub.3 of the node 8 can be written as (0, 0, *, *) * stands for don't care
FIG. 6 illustrates an example of logic functions and permissible functions of circuits and a circuit optimizing process using those functions. More specifically, FIG. 6(a) illustrates the output logic of each of gates C, D and E when an input X.sub.1 is changed in the order of 0, 0, 1, 1 and an input X.sub.2 is changed in the order of 0, 1, 0, 1. FIG. 6(b) illustrates permissible functions of the gates A, B, C and D and inputs X.sub.1 and X.sub.2 which keep the output of the circuit (gate E) in the order of 0, 1, 1, 0.
FIG. 6(c) illustrates a logic circuit implemented with EX-OR circuits and FIG. 6D illustrates permissible functions for the EX-0R circuits. In FIG. 6(e), since the permissible functions of gates F and G in FIG. 6(d) are common EQU (0, 1, 1, *),
gates F and G are merged into a gate F which implements the common part in their permissible functions.
Furthermore, FIGS. 6(f) and 6(g) illustrate a redundant-net removing process. A gate L with permissible function EQU (*, *, *, *)
and nets in FIG. 6(f) can be removed for conversion to a circuit with no redundancy, as shown in FIG. 6(g).
In method B, no use is made of intermediate nodes so that, unlike the method A, there is no "combination of values that can never take place." However, a multistage expression of a logical expression containing intermediate nodes represents the topology of a circuit, while a truth table merely represents a logic function implemented by each node. Thus, it should be noted that a truth table is not a representation itself of a circuit. Therefore, a process slightly different from that in method A must be performed. Generally, to perform optimization, some transformation of an expression is performed such that a change in the logic function is involved in don't care conditions. (In method B, transformations are not performed indiscriminately to undergo subsequent checks. The kinds of transformations to be performed are determined previously from don't-care conditions. On this point, method B is quite distinct from method A.)
Method B also permits powerful optimization. In this case, however, the amount of memory must always be proportional to the exponent of an input variable. Furthermore, the same amount of trouble is necessary in calculation. Handling of a 10-to-20-input circuit is the limits of the fastest computers of today.